package com.atguigu.stack;

import java.awt.event.FocusEvent;
import java.security.PublicKey;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author shkstart
 * @create 2021-08-09 18:43
 */
public class PolandNotation {
    public static void main(String[] args) {
        //创建后缀表达式
//        String suffixExpression="30 4 + 5 X 6 -";
//        String suffixExpression="4 5 X 8 - 60 + 8 2 / +";
////        List<String> rpnlist = getListString(suffixExpression);
////        System.out.println("rpnlist="+rpnlist);
////        int res = calculate(rpnlist);
////        System.out.println("计算的结果是="+res);
        String expression="1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println("转化为集合的中缀表达式："+infixExpressionList);
        //转化后缀表达式
        List<String>  suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
        //进行计算
        System.out.println("后缀表达式："+suffixExpreesionList);

        int result = calculate(suffixExpreesionList);
        System.out.println("计算的最终结果："+result);

    }

public static List<String> parseSuffixExpreesionList(List<String> ls) {
    //定义两个栈
    Stack<String> s1 = new Stack<String>(); // 符号栈
    //说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
    //因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
    //Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
    List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2

    //遍历ls
    for(String item: ls) {
        //如果是一个数，加入s2
        if(item.matches("\\d+")) {
            s2.add(item);
        } else if (item.equals("(")) {
            s1.push(item);
        } else if (item.equals(")")) {
            //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
            while(!s1.peek().equals("(")) {
                s2.add(s1.pop());
            }
            s1.pop();//!!! 将 ( 弹出 s1栈， 消除小括号
        } else {
            //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
            //问题：我们缺少一个比较优先级高低的方法
            while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) {
                s2.add(s1.pop());
            }
            //还需要将item压入栈
            s1.push(item);
        }
    }

    //将s1中剩余的运算符依次弹出并加入s2
    while(s1.size() != 0) {
        s2.add(s1.pop());
    }

    return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List

}
    //将中缀表达式转化为集合
    public static List<String> toInfixExpressionList(String s){
        //建立集合
        ArrayList<String> ls = new ArrayList<>();
        //扫描的定位
        int i=0;
        //拼接的存在
        String str="";
        //临时储存
        char c;
        do {
            //如果是字符
            if ((c=s.charAt(i))<47||(c=s.charAt(i))>58) {
                ls.add(c+"");
                i++;
            }
            //如果是数字
            else {
                str ="";
                //进行拼接
                while (i<s.length()&&(c=s.charAt(i))>=47&&(c=s.charAt(i))<=58){
                    str+=c;
                    i++;
                }
                ls.add(str);
            }
        }while (i<s.length());
        return ls;


    }
    //分隔空格
    public static List<String> getListString(String suffixExpression){
        String[] split = suffixExpression.split(" ");
        ArrayList<String> list = new ArrayList<>();
        for(String ele:split ){
            list.add(ele);
        }
        return list;
    }
    //逆波兰运算
    public static int calculate(List<String> ls){
        //创建栈
        Stack<String> stack = new Stack<>();

        //遍历集合
        for (String item:ls){
            //如果是数字，则加栈
            if (item.matches("\\d+")){
                stack.push(item);

            }else {
                //如果是符号，则跳出两个数字，进行运算
                int num2=Integer.parseInt(stack.pop());
                int num1=Integer.parseInt(stack.pop());
                int res=0;
                if (item.equals("+")){
                    res=num1+num2;
                }
                else if (item.equals("-")){
                    res=num1-num2;
                }
                else if (item.equals("*")){
                    res=num1*num2;
                }
                else if (item.equals("/")){
                    res=num1/num2;
                }else {
                    throw new RuntimeException("运算符有误");
                }
                //计算出来的加入栈中
                stack.push(String.valueOf(res));
            }

        }
        //返回最后的结果
        return Integer.parseInt(stack.pop());
    }
}
//比较运算符符号的优先级
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;
    public static int getValue(String operation){
        int result=0;
        switch (operation){
            case "+":
                result=ADD;
                break;
            case "-":
                result=SUB;
                break;
            case "*":
                result=MUL;
                break;
            case "/":
                result=DIV;
                break;
//            default:
//                System.out.println("不存在运算符！");
//                break;

        }
        return result;
    }

}